// https://leetcode.cn/problems/number-of-matching-subsequences/
// Created by ade on 2022/11/17.
//
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>

using namespace std;

class Solution {
public:
    int numMatchingSubseq(string s, vector <string> &words) {
//        这种方法会超时
//        vector<int> points(words.size());
//        int num = 0;
//        for (auto &c:s) {
//            for (int i = 0; i < points.size(); i++) {
//                if (points[i] == words[i].size()) continue;
//                if (words[i][points[i]] == c) {
//                    points[i]++;
//                    if (points[i] == words[i].size()) num++;
//                }
//            }
//        }
//        return num;

        // 改进后
        vector < queue < pair < int, int >> > queues(26);// first-words中的index second-单词的指针位置
        for (int i = 0; i < words.size(); i++) queues[words[i][0] - 'a'].push({i, 0});
        int res = 0;
        for (char c : s) { // 这里不能用auto,切记，否则是int类型
            auto &q = queues[c - 'a'];
            int size = q.size();
            while (size--) {
                int i = q.front().first;
                int j = q.front().second;
                q.pop();
                ++j;
                if (j == words[i].size()) {
                    res++;
                } else {
                    queues[words[i][j] - 'a'].push({i, j});
                }
            }
        }
        return res;
    }

};

int main() {
    Solution so;
    string s = "kguhsugfxvwxakdcovjeczhqvbevkhlixsrhumxykbkihjdfxxxwragzcbhngbzgasxysxdtwntvbpdihtvkffacmxhbxxqniyqm";
    vector <string> ss = {
            "ykbkihjdfxxxwragzcbhngbzgasxysxdtwn",
                          "wxakdcovjeczhqvbevkhlixsrhumxykbkihj",
                          "diht",
                          "covjeczhqvbevkhlixsrhumxykbkihjdfxxxwragzcbhngbz",
                          "ovjeczhqvbevkhlixsrhumxykbkihjdfxxxwragzcbhng"
                          "qhzucvqxalfrtlrdjverseuldzymzbunhugekoyyghmkpkfqmd",
                          "eydmbsorvjnnifqxsyuypsrijzrosukrhtbneprpyyoawbvoki",
                          "uanfzlfmmtvhzzebrazyuslbapsfzwtlvqbhqxsfmqagwxetro",
                          "fffaawedchlcyqvzzxbzczbwyfjkllpsjhoozyresqemmawban",
                          "astrknwzefcmuswdxalooatmiduspjuofthtomoqilgdojwhon"
    };
    cout << so.numMatchingSubseq(s, ss) << endl;
    return 0;
}